package com.mlamp动态规划问题;

import java.util.*;

public class 两个字符串所有的公共子序列 {

    /**
     * 求取两个字段所有的子序列
     *
     * @param inputA
     * @param inputB
     * @return
     */
    public static List<String> exactAllCommonSeq(String inputA, String inputB) {
        //把字符串转成字符数组
        char[] arr1 = inputA.toCharArray();
        char[] arr2 = inputB.toCharArray();
        int arr1_len = arr1.length, arr2_len = arr2.length;
        // 把两个字符串分别以行和列组成一个二维矩阵
        int[][] temp = new int[arr1_len][arr2_len];
        //初始化二维矩阵中的第一列
        for (int j = 0; j < arr1.length; j++) {
            temp[j][0] = (arr2[0] == arr1[j]) ? 1 : 0;
        }

        //初始化二维矩阵中的第一行
        for (int i = 0; i < arr2.length; i++) {
            temp[0][i] = (arr1[0] == arr2[i]) ? 1 : 0;
        }

        //嵌套for循环：比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0
        for (int i = 1; i < arr1.length; i++) {
            for (int j = 1; j < arr2.length; j++) {
                if (arr1[i] == arr2[j]) {
                    //对角线上一个值加1，方便求取每个公共子序列的长度
                    temp[i][j] = temp[i - 1][j - 1] + 1;
                } else {
                    temp[i][j] = 0;
                }
            }
        }

        List<Map<String, Integer>> list = new ArrayList<>();
        //依次遍历对角矩阵的对角线
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr2.length; j++) {
                Map<String, Integer> map = new HashMap<>();
                if (temp[i][j] != 0 && temp[i][j] != 1) {
                    if (temp[i - 1][j - 1] == temp[i][j] - 1) {
                        if (i - 1 > 0 && j - 1 > 0 && i + 1 < arr1.length && j + 1 < arr2.length && temp[i - 1][j - 1] != 0 && temp[i + 1][j + 1] == 0) {
                            map.put("row", i);
                            map.put("column", j);
                            map.put("length", temp[i][j]);
                            list.add(map);
                        } else if ((i + 1 == arr1.length || j + 1 == arr2.length)) {
                            map.put("row", i);
                            map.put("column", j);
                            map.put("length", temp[i][j]);
                            list.add(map);
                        }
                    }
                }
            }
        }

        List<String> resultList = new ArrayList<>();
        if (!list.isEmpty()) {
            for (Map<String, Integer> map : list) {
                String s = getsubString(inputA, map.get("row"), map.get("length"));
                resultList.add(s);
            }
        }
        return resultList;
    }

    /**
     * 根据坐标位置及子串长度获取子串内容
     *
     * @param s
     * @param a
     * @param b
     * @return
     */
    public static String getsubString(String s, int a, int b) {
        String s1;
        s1 = s.substring(a - b + 1, a + 1);
        return s1;
    }


    /**
     * 测试方法
     *
     * @param args
     */
    public static void main(String[] args) {
        String inputA = "我爱你，中国";
        String inputB = "我爱你，我是中国人";
        System.out.println(exactAllCommonSeq(inputA, inputB));
        System.out.println(LCS(inputA, inputB));

        inputA = "BDCABA";
        inputB = "ABCBDAB";
        System.out.println(LCS(inputA, inputB));

        System.out.println(a(inputA, inputB));
        inputA = "我爱你，中国";
        inputB = "我爱你，我是中国人";
        System.out.println(a(inputA, inputB));
    }


    public static int a(String s1, String s2) {
        int[][] c = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            c[i][0] = 0;
        }
        for (int i = 0; i <= s2.length(); i++) {
            c[0][i] = 0;
        }
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                }
            }
        }
        return c[s1.length()][s2.length()];
    }

    public static int LCS(String s1, String s2) {
        int[][] c = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            c[i][0] = 0;
        }
        for (int i = 0; i <= s2.length(); i++) {
            c[0][i] = 0;
        }
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    c[i][j] = Math.max(c[i][j - 1], c[i - 1][j]);
                }
            }
        }
        return c[s1.length()][s2.length()];
    }


}
